package com.example.hot100;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
 *
 *  示例 1：
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 *
 *  示例 2：
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 */
public class Leetcode560_SubArraySum {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        int k = 2;

//        nums = new int[] {1, 2, 3};
//        k = 3;

        System.out.println(new Solution().subarraySum(nums, k));
    }

    static class Solution {
        private int subarraySum2(int[] nums, int k) {
            return 0;
        }

        /**
         * 前缀和
         * @param nums
         * @param k
         * @return
         */
        private int subarraySum1(int[] nums, int k) {
            long preSum = 0;
            int res = 0;
            Map<Long, Integer> map = new HashMap<>();
            map.put(0L, 1);
            for (int i = 0; i < nums.length; i++) {
                preSum += nums[i];
                res += map.getOrDefault(preSum - k, 0);
                map.put(preSum, map.getOrDefault(preSum, 0) + 1);
            }
            return res;
        }

        public int subarraySum(int[] nums, int k) {
            return subarraySum1(nums, k);
        }
    }
}
